package MyTree;

import java.util.HashMap;
import java.util.List;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 * 例如，给出
 *
 * 中序遍历 inorder = [9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 *
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 */
public class Leetcode0106 {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(inorder, postorder, indexMap, 0, n - 1, 0, n - 1);
    }

    public static TreeNode myBuildTree(int[] in, int[] post, HashMap<Integer, Integer>indexMap, int in_start, int in_end, int post_start, int post_end){
        if (post_start > post_end) {
            return null;
        }

        int post_root = post_end;
        int in_root = indexMap.get(post[post_root]);
        int left_len = in_root - in_start;
        TreeNode tree = new TreeNode(post[post_root]);

        tree.left = myBuildTree(in, post, indexMap, in_start, in_root-1, post_start, post_start+left_len-1);
        tree.right = myBuildTree(in, post,indexMap,in_root+1, in_end,post_start+left_len, post_end-1);
        return tree;
    }

    public static void main(String[] args) {
        int[] post = {9,15,7,20,3};
        int[] in = {9,3,15,20,7};
        TreeNode tree = buildTree(in, post);

        List<Integer> root = TreeUtils.preorderTraversal(tree);
        System.out.println(root.toString());
    }

}
